Public Key Cryptography and the RSA algorithm

Public Key Cryptography

An introduction

A good cryptographic algorithm requires two things: security and authentication. An algorithm is secure if it allows information to be transmitted from one party to another with only the intended recipient being able to read the message. It provides authentication if there exists a way for the recipient to verify who sent the message.

Both of these criteria are met in the algorithms covered thus far, such as Caesar and one-time pad, through use of a symmetric key. In these algorithms, both the sender and the receiver share a key that is used to encrypt and decrypt a message, and is not shared with anyone else. Security is provided through the fact that only the sender and receiver have access to the key, and thus only these two individuals can decrypt the message. Thus, as long as the encryption algorithm itself is strong, the secret key provides security. As we have covered, the Caesar algorithm can be cracked by a third party in other ways, such as statistical analysis of letter frequency, and thus it does not provide as robust security as the one-time-pad algorithm, which uses keys with lengths equal to message lengths and does not repeat keys. Authentication is provided through the symmetric key through the fact that only the sender and receiver are able to create an encrypted message (assuming the key has not been compromised), meaning the message must have come from the presumed sender.

However, these algorithms raise a critical question: How will we exchange the key between the two parties in the first place without holding a physical meeting?

The history

The cryptographic techniques seen in class thus far all rely on a shared symmetric key, but provide no secure way of exchanging this key electronically. This has become increasingly important in the modern world, as secure electronic communication between two parties who have never met in person, such as e-mail, chat applications, and electronic bank payments, have become pervasive.

With the electronic world on the horizon, this became a popular problem in the 1970s, causing many people to consider various solutions. One of the solutions, conceptualized in 1976 by Whitfield Diffie and Martin Hellman, is public key cryptography. Rather than use one shared key, a pair of keys are used that can undo each other. The encryption key is made public, by publication to the web, for instance, and the decryption key is kept private.¹.

It is important that the keys are mathematically linked, but knowing the public key and a message encrypted with either key, it is still mathematically infeasible to compute the private key. ² Diffie and Hellman suggested this be done using trapdoor one-way functions, but did not provide a mathematical algorithm for this.¹ It was not until 1978 when Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology provided the RSA algorithm, mathematical procedure to produce keys, making public key cryptography a viable solution to the key-exchange problem.³

Security

If a user chooses to communicate using a public key cryptographic system, they must first create their keys. Here, we will call E_A the public key and D_A the private key. These keys are paired, so if a message is encrypted with one, it can be recovered by then decrypting it with the other.

That is:

\[ \begin{aligned}D_{A} ( E_{A}(M)) = M\\ E_{A} ( D_{A}(M)) = M \end{aligned} \]

Say Artemis wants to securely transmit a message to Melaine. She will first write her message (\(\mu\)), then retrieve Melanie’s public key (E_M), which is published online, and use it to encrypt her message to produce the ciphertext:

\[ \begin{aligned}E_{M} (\mu) = ciphertext \end{aligned} \]

Artemis now can securely transmit this to Melanie, since only Melanie’s private key can decrypt the message, and she alone has access to it. Melanie receives the ciphertext from Artemis, and uses her private key (D_M) to decrypt the message to reveal the original plaintext.

\[ \begin{aligned}D_{M} ( E_{M}(\mu)) = \mu = plaintext \end{aligned} \]

Melanie can now can read Artemis’ message.

This process alone does not provide authentication, since Melanie’s public key is available to anyone, meaning that anyone is able to send a message to Melanie, and she cannot be sure of who the message is from.

Authentication

In order to verify that the message received came from Artemis, it is important that she signs the message in the same way one would do when sending paper mail. Using public key cryptography, it is possible to prove that the message indeed came from Artemis and detect if a signature has been forged. It is important that electronic signatures are message-dependent and signer-dependent. In other words, the signature must be linked to the message mathematically to prevent modification of the signature or the message.

Assume Artemis wants to send a message to Melanie that is signed (though not secure). Artemis will use her private key to encrypt the message:

\[ \begin{aligned}D_{A} (\mu) = ciphertext \end{aligned} \]

Artemis then sends this ciphertext to Melanie. When she recieves it, she decrypts it using Artemis’ public key:

\[ \begin{aligned}E_{A} ( D_{A}(\mu)) = \mu = plaintext \end{aligned} \]

Although anyone can read the message, since everyone has access to Artemis’ public key, Artemis’ use of the private key, which only she has access to, acts as a signature. That is, since Artemis’ public key was able to decrypt the ciphertext, it must have been originally encrypted with her private key, and thus the message must be coming from her.

Putting it together

In order for a message to be both secure and authenticated, these two methods must be merged. This is done by applying the functions on top of each other. That is, if Artemis wants to send a message to Melanie that is both secure and signed, she will first secure it by applying Melanie’s public key:

\[ \begin{aligned}E_{M}(\mu) \end{aligned} \]

Then authenticate it by applying her own private key: \[ \begin{aligned}D_{A} ( E_{M}(\mu)) = ciphertext \end{aligned} \]

Artemis then sends this to Melanie.

Melanie will recieve this ciphertext and authenticate it by applying Artemis’ public key:

\[ \begin{aligned}E_{A}(D_{A} ( E_{M}(\mu))) = E_{M}(\mu) \end{aligned} \]

And then complete the secure transfer of information by decrypting it with his private key:

\[ \begin{aligned}D_{M} ( E_{M}(\mu)) = \mu = plaintext \end{aligned} \]

Visual demonstration

All of these letters and functions can be confusing, we know! So, below we provide a way to understand how public key cryptography provides security and authentication visually.

Again, say Artemis wants to send a message to Melanie.

Both Artemis and Melanie’s public keys are available on the web.

1.) Artemis writes her message and authenticates it using Melanie’s public key to produce the encrypted message here shown as a small orange envelope

———–>

2.) Now that the message has been secured, Artemis will sign it with her private key, shown by the large purple envelope. This produces the final ciphertext. Artemis sends this to Melanie.

———–>

3.) To verify that the message was sent from Artemis, Melanie first uses Artemis’ public key to decrypt the message. Since the message can be decrypted with Artemis’ public key, it must have been encrypted with her private key, meaning it was sent from her.

4.) Melanie then decrypts the message with her private key, which only she can do.

5.) The message is now decrypted!

The RSA algorithm

The methods described above offer a hypothetical cryptographic technique. However, to fully implement this, there needs to be a way to generate the public and private keys. In 1978, the RSA algorithm was created to do just that.

Mathematical Principle

RSA is a trapdoor one way function based on the principle that multiplication is harder than factorization. The RSA algorithm is based on 6 mathematical theorems ⁴

1. Fundamental prime number theorem of mathematics
   
2. Euclid theorem
   
3. Fermat theorem
   
4. If p and q are all prime numbers and $p ≠q $, then $(pq)=(p)(q)=(p−1)(q−1).
5. Euler theorem
6. If p and q are prime numbers and \(p ≠ q\) , \(rm ≡ 1 (mod( p − 1)(q − 1))\) , a is any positive integer, \(b≡a^{m}mod( pq)\),\(c≡b^{r}mod(pq)\), then \(c≡amod(pq)\).

RSA digital signature algorithm is described as follows. ⁵

1. Select two prime numbers p and q. Then compute their product n=pq
   example: p=5 and q=11, n= pq = 55

2. Select an odd public exponent e between 3 and n-1 that is relatively prime to p-1 and q-1. That is, gcd(5, e) = 1 and gcd(11, e) =1
   example: choose public exponent e=3

3. The private exponent d is equal to \(e^{-1} mod(20)\). It is calculated using Euclid algorithm, in which d satisfies \(ed ≡ 1 (mod( p − 1)(q − 1))\).
   example: private exponent \(d= 3^{-1} mod(20) = 7\)

To encrypt and produce the ciphertext, we do \(m^e mod(n)\) example: \(c = m^3 mod(55)\)

To decrypt the message and recover the plaintext, we do \(c^d mod(n)\) example: \(m = c^7 mod(55)\)

Conclusions

Our assessment

We think that public key cryptography, and the use of the asymmetric key, is an extremely interesting and innovative way to solve the key exchange problem. Although it has not been proven that this type of factorization is truly a trapdoor function, this is a much stronger and more practical encryption technique to the ones seen previously in class (Caesar, one-time pad, etc). This is exemplified by the fact that the RSA algorithm continues to be used today, in various electronic communications where the two parties cannot meet in person, such as e-mail, chat applications, and VPNs.⁶

Shortcomings/challenges

Although the technique we described above is quite robust, it still has a few issues. Chief among them is the fact that there needs to be a way to verify that a published public key truly belongs to the listed owner. That is, a malicious third party, Eve, could publish their own public key and label it as Melanie’s, for example. Then, when Artemis tries to communicate with Melanie, she is actually communicating with Eve. Certificates have been developed to combat this issue. Other issues include weaknesses in the hardware being used, such as dropped information, and the fact that sending time and decryption time can be monitored and clue in information about the key, such as key length. However, these issues have surely been addressed, since the algorithm is still in effect for many systems throughout the world today.

Team Contributions

Melanie and Artemis worked together on the blog post. Artemis wrote the introduction, history, security, putting it together, and conclusion sections, and created the webpage. Melanie created and photographed the visual representation props, and wrote the authentication and RSA algorithm sections.

References

---

---

1. Diffe, W. and Hellman, M. New Directions in Cryptography. IEEE Transactions on Information Theory, Vol. 22 No. 6, November 1976. https://ee.stanford.edu/~hellman/publications/24.pdf↩

2. Global Sign What is public-key cryptography?. 2019. https://www.globalsign.com/en/ssl-information-center/what-is-public-key-cryptography/↩

3. Rivest, R., Shamir, A. and Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Massachusetts Institute of Technology, 1978. https://people.csail.mit.edu/rivest/Rsapaper.pdf↩

4. Cao, Y. and Fu, C. An Efficient Implementation of RSA Digital Signature Algorithm. International Conference on Intelligent Computation Technology and Automation, 2008. https://ieeexplore.ieee.org/document/4659731↩

5. Kaliski, B. The Mathematics of the RSA Public-Key Cryptosystem. RSA Laboratories. http://www.mathaware.org/mam/06/Kaliski.pdf↩

6. University of Massachusetts. The RSA encryption algorithm http://www.ecs.umass.edu/ece/koren/FaultTolerantSystems/simulator/RSA/new_page_5.htm↩